package sortStudy;

import java.util.Random;

public class QuickSort2 {

    public static Random random = new Random();

    public static void main(String[] args) {
        int[] nums = new int[]{/*2, 1, 7, 9, 4, 6, 8, 3*/};
        quickSelect(nums, 0, nums.length - 1);
        for (int i = 0; i < nums.length; i++){
            System.out.println(nums[i]);
        }
    }

    //进行快排
    public static void quickSelect(int[] arr, int l, int r){
        if (l >= r){
            return;
        }
        int index = partition(arr, l, r);
        quickSelect(arr, l, index - 1);
        quickSelect(arr, index + 1, r);
    }

    //确定元素位置
    public static int partition(int[] arr, int l, int r){
        //确定分界元素的位置
        int i = random.nextInt(r - l + 1) + l;
        swap(arr, i, r);
        int key = arr[r];
        int m = l - 1;
        //将小的值向前放
        for (int j = l; j < r; j++){
            if (arr[j] < key){
                swap(arr, ++m, j);
            }
        }
        swap(arr, m + 1, r);
        return m + 1;
    }

    //交换两个元素位置
    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
